//
// Description: 309. 最佳买卖股票时机含冷冻期
// Created by Loading on 2022/4/9.
//

#include <bits/stdc++.h>

using namespace std;

int maxProfit(vector<int> &prices) {
    int n = prices.size();
    // dp[i][0] 表示第i天结束时，未持有股票，且不处于冷冻期时的最大收益
    // dp[i][1] 表示第i天结束时，未持有股票，且处于冷冻期时的最大收益
    // dp[i][2] 表示第i天结束时，持有股票时的最大收益
    vector<vector<int>> dp(n, vector<int>(3));
    /* dp[0][0]，第一天没有任何动作，收益为0 */
    /* dp[0][1]，理论上第一天结束不能进入冷冻期，这里可以理解为当天买入后卖出，进入冷冻期，收益为0 */
    /* dp[0][2]，第一天买入，收益为负 */
    dp[0][2] = -prices[0];
    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][2] + prices[i];
        dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] - prices[i]);
    }

    /* 无需比较dp[n - 1][2]，最后一天仍持有股票收益一定比不持有低 */
    return max(dp[n - 1][0], dp[n - 1][1]);
}

int main() {
    vector<int> prices{1, 2, 3, 0, 2};
    int res = maxProfit(prices);
    cout << res << endl;

    return 0;
}